一.数论函数
1.定义
数论函数是 : 其定义域是正整数,值域是一个数集的函数。
积性函数 : 对于所有互质 整数 a a a 和 b b b 有性质f ( a b ) = f ( a ) f ( b ) f(ab)=f(a)f(b) f ( a b ) = f ( a ) f ( b ) 的数论函数。
完全积性函数 : 对于所有整数 a a a 和 b b b 有性质f ( a b ) = f ( a ) f ( b ) f(ab)=f(a)f(b) f ( a b ) = f ( a ) f ( b ) 的数论函数。
常见的的积性函数:
2.性质
1.对于任意正整数 n n n , ∑ i ∣ n φ ( i ) = n \sum_{i|n}\varphi(i)=n ∑ i ∣ n φ ( i ) = n
不妨令 f ( n ) = ∑ i ∣ n φ ( i ) f(n)=\sum_{i|n}\varphi(i) f ( n ) = ∑ i ∣ n φ ( i ) , 首先证明 f f f 是一个积性函数。
因为 n , m n , m n , m 互质
f ( n ) ∗ f ( m ) = ∑ i ∣ n φ ( i ) × ∑ j ∣ m φ ( j ) f(n)*f(m)=\sum_{i|n}\varphi(i) \times \sum_{j|m}\varphi(j)
f ( n ) ∗ f ( m ) = i ∣ n ∑ φ ( i ) × j ∣ m ∑ φ ( j )
= ∑ i j ∣ n m φ ( i ) × φ ( j ) ~~~~~~~~~~~~~~~~~=\sum_{ij|nm}\varphi(i) \times \varphi(j)
= i j ∣ n m ∑ φ ( i ) × φ ( j )
= ∑ i j ∣ n m φ ( i j ) ~~~~~~=\sum_{ij|nm}\varphi(ij)
= i j ∣ n m ∑ φ ( i j )
= f ( n × m ) ~~~~~=f(n \times m)
= f ( n × m )
因为 n = p 1 w 1 × p 2 w 2 × . . . × p k w k n=p_1^{w_1} \times p_2^{w_2} \times ... \times p_k^{w_k} n = p 1 w 1 × p 2 w 2 × . . . × p k w k , 且 f f f 为积性函数 , 所以只需求出 f ( p i w i ) f(p_i^{w_i}) f ( p i w i ) 即可。
f ( p i w i ) = ∑ d ∣ p i w i φ ( d ) f(p_i^{w_i})=\sum_{d|p_i^{w_i}}\varphi(d)
f ( p i w i ) = d ∣ p i w i ∑ φ ( d )
= φ ( 1 ) + φ ( p i ) + φ ( p i 2 ) + . . . + φ ( p i w i ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=\varphi(1)+\varphi(p_i)+\varphi({p_i}^2)+...+\varphi({p_i}^{w_i})
= φ ( 1 ) + φ ( p i ) + φ ( p i 2 ) + . . . + φ ( p i w i )
= 1 + ( p i − 1 ) + ( p i 2 − p i ) + . . . + ( p i w i − p i w i − 1 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=1+(p_i-1)+({p_i}^2-p_i)+...+({p_i}^{w_i}-{p_i}^{w_i-1})
= 1 + ( p i − 1 ) + ( p i 2 − p i ) + . . . + ( p i w i − p i w i − 1 )
= p i w i ~~~={p_i}^{w_i}
= p i w i
所以 f ( n ) = n f(n)=n f ( n ) = n , 即 ∑ i ∣ n φ ( i ) = n \sum_{i|n}\varphi(i)=n ∑ i ∣ n φ ( i ) = n 。
2.对于任意正整数 n n n , ∑ i ∣ n μ ( i ) = [ n = 1 ] \sum_{i|n}\mu(i)=[n=1] ∑ i ∣ n μ ( i ) = [ n = 1 ]
证明如下:
1.当 n = 1 n=1 n = 1 时显然
2.当 n ! = 1 n!=1 n ! = 1 时,由唯一分解定理得:n = p 1 w 1 p 2 w 2 . . . p k w k n=p_1^{w_1}p_2^{w_2}...p_k^{w_k} n = p 1 w 1 p 2 w 2 . . . p k w k
由莫比乌斯函数的性质,μ ( k ) = 0 \mu(k) \not= 0 μ ( k ) = 0 当且仅当 k k k 无平方因子。(由多个质因子相乘)
有 i i i 个质因子的数有 C k i C_k^i C k i 种取值。
所以只需证
∑ i = 0 k ( − 1 ) i C k i = 0 \sum_{i=0}^k(-1)^iC_k^i=0
i = 0 ∑ k ( − 1 ) i C k i = 0
很像二项式定理,将 x = 1 , y = − 1 x = 1 , y = -1 x = 1 , y = − 1 代入即可得证。
3.对于任意正整数 n n n ,∑ d ∣ n μ ( d ) d = φ ( n ) n \sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n} ∑ d ∣ n d μ ( d ) = n φ ( n )
这个一会儿再证。
二.狄利克雷卷积
两个数论函数 f f f 和 g g g 的卷积为 t ( n ) = ( f × g ) ( n ) = ∑ d ∣ n f ( d ) × g ( n d ) t(n)=( f \times g )(n)=\sum_{d|n}f(d) \times g(\frac{n}{d}) t ( n ) = ( f × g ) ( n ) = ∑ d ∣ n f ( d ) × g ( d n ) 。
前面的括号代表将 f f f 卷 g g g ,后面的括号代表范围。
简记为t = f ∗ g t=f*g t = f ∗ g 。
狄利克雷卷积满足交换律,结合律与分配律。
若 f f f 是任意积性函数 , 则 f ∗ ϵ = f f*\epsilon=f f ∗ ϵ = f
较为常见数论函数的迪利克雷卷积:
d = I ∗ I d = I * I
d = I ∗ I
σ = i d ∗ I σ = id * I
σ = i d ∗ I
i d = φ ∗ I id=\varphi * I
i d = φ ∗ I
ϵ = μ ∗ I \epsilon = \mu * I
ϵ = μ ∗ I
φ = μ ∗ i d φ = μ* id
φ = μ ∗ i d
其中,后三项分别对应积性函数的三个性质。
现在证一下 φ = μ ∗ i d φ = μ* id φ = μ ∗ i d
φ ∗ I = i d \varphi * I=id
φ ∗ I = i d
φ ∗ I ∗ μ = i d ∗ μ \varphi*I*\mu=id*\mu
φ ∗ I ∗ μ = i d ∗ μ
φ = i d ∗ μ \varphi=id*\mu
φ = i d ∗ μ
即
φ ( n ) = ∑ d ∣ n n d ∗ μ ( d ) \varphi(n)=\sum_{d|n}\frac{n}{d}*\mu(d)
φ ( n ) = d ∣ n ∑ d n ∗ μ ( d )
两边同时除以 n n n , 得
φ ( n ) n = ∑ d ∣ n μ ( d ) d \frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}
n φ ( n ) = d ∣ n ∑ d μ ( d )
就是上文提到的性质3 3 3 。
三.数论分块
1.引入
题目给你这样一个式子:
∑ i = 1 n ⌊ k i ⌋ \sum_{i=1}^{n}\lfloor\frac{k}{i} \rfloor
i = 1 ∑ n ⌊ i k ⌋
这不是暴力吗?
那如果n ≤ 1 0 12 n \le 10^{12} n ≤ 1 0 1 2 呢?再见
这时我们就要用到一个神奇的结论——数论分块
2.思想
再看一眼式子,我们发现,很多值是一样的。
如n = 6 , k = 3 n=6,k=3 n = 6 , k = 3 ,⌊ 3 4 ⌋ = ⌊ 3 5 ⌋ = ⌊ 3 6 ⌋ \lfloor \frac{3}{4} \rfloor = \lfloor \frac{3}{5} \rfloor = \lfloor \frac{3}{6} \rfloor ⌊ 4 3 ⌋ = ⌊ 5 3 ⌋ = ⌊ 6 3 ⌋
如果我们知道分布规律,那么这一段就可以一起求解了。
结论是:若一段区间的左端点为l l l ,那么区间值为 ⌊ n l ⌋ \lfloor \frac{n}{l} \rfloor ⌊ l n ⌋ ,区间右端点 r = ⌊ n ⌊ n l ⌋ ⌋ r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor r = ⌊ ⌊ l n ⌋ n ⌋
证明如下:
设 k = ⌊ n l ⌋ , p = n m o d l k=\lfloor \frac{n}{l} \rfloor , p=n~mod~l k = ⌊ l n ⌋ , p = n m o d l , 则n = k ∗ l + p n=k*l+p n = k ∗ l + p
若 ⌊ n l + d ⌋ = k \lfloor \frac{n}{l+d} \rfloor = k ⌊ l + d n ⌋ = k , 则 n = k ∗ ( l + d ) + p ′ n = k*(l+d)+p' n = k ∗ ( l + d ) + p ′
两个式子相减得:p ′ = p − k d p'=p-kd p ′ = p − k d , 又因为 0 ≤ p , p ′ ≤ l − 1 0 \le p,p' \le l-1 0 ≤ p , p ′ ≤ l − 1
所以 d d d 的最大值为 ⌊ p k ⌋ \lfloor \frac{p}{k} \rfloor ⌊ k p ⌋ 。
那么,
r = l + d r=l+d
r = l + d
= l + ⌊ p k ⌋ ~~~~~~~~ =l+\lfloor \frac{p}{k} \rfloor
= l + ⌊ k p ⌋
= l + ⌊ n m o d l ⌊ n l ⌋ ⌋ ~~~~~~~~~~~~~~~~~~~ =l+\lfloor \frac{n~mod~l}{ \lfloor \frac{n}{l} \rfloor } \rfloor
= l + ⌊ ⌊ l n ⌋ n m o d l ⌋
= l + ⌊ n − ⌊ n l ⌋ ∗ l ⌊ n l ⌋ ⌋ ~~~~~~~~~~~~~~~~~~~~~~~~~ =l+\lfloor \frac{n- \lfloor \frac{n}{l} \rfloor *l}{ \lfloor \frac{n}{l} \rfloor } \rfloor
= l + ⌊ ⌊ l n ⌋ n − ⌊ l n ⌋ ∗ l ⌋
= ⌊ l + n − ⌊ n l ⌋ ∗ l ⌊ n l ⌋ ⌋ ~~~~~~~~~~~~~~~~~~~~~~~~~ =\lfloor l+ \frac{n- \lfloor \frac{n}{l} \rfloor *l}{ \lfloor \frac{n}{l} \rfloor } \rfloor
= ⌊ l + ⌊ l n ⌋ n − ⌊ l n ⌋ ∗ l ⌋
= ⌊ ⌊ n l ⌋ ∗ l ⌊ n l ⌋ + n − ⌊ n l ⌋ ∗ l ⌊ n l ⌋ ⌋ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ =\lfloor \frac{\lfloor \frac{n}{l} \rfloor*l}{\lfloor \frac{n}{l} \rfloor} + \frac{n- \lfloor \frac{n}{l} \rfloor *l}{ \lfloor \frac{n}{l} \rfloor } \rfloor
= ⌊ ⌊ l n ⌋ ⌊ l n ⌋ ∗ l + ⌊ l n ⌋ n − ⌊ l n ⌋ ∗ l ⌋
= ⌊ n ⌊ n l ⌋ ⌋ ~~~~~~~ =\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor}\rfloor
= ⌊ ⌊ l n ⌋ n ⌋
3.代码实现
for( int l = 1 , r ; l <= n ; l = r + 1 ) {
r = n / (n / l);
\\具体内容例题会讲到
}
数论分块大多数情况是和数论函数一起使用
4.例题
题目要求的是
∑ i = 1 n k m o d i \sum_{i=1}^nk~mod~i
i = 1 ∑ n k m o d i
⇒ ∑ i = 1 n k − ⌊ k i ⌋ ∗ i \Rightarrow \sum_{i=1}^n k-\lfloor \frac{k}{i} \rfloor * i
⇒ i = 1 ∑ n k − ⌊ i k ⌋ ∗ i
⇒ n ∗ k − ∑ i = 1 n ⌊ k i ⌋ ∗ i \Rightarrow n*k-\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor * i
⇒ n ∗ k − i = 1 ∑ n ⌊ i k ⌋ ∗ i
然后 ,因为在 l − r l-r l − r 区间内 ⌊ k i ⌋ \lfloor \frac{k}{i} \rfloor ⌊ i k ⌋ 的值相等,i i i 递增,所以这段区间内是一个等差数列 ( 首项为 l ∗ ⌊ k i ⌋ l*\lfloor \frac{k}{i} \rfloor l ∗ ⌊ i k ⌋ , 末项为 r ∗ ⌊ k i ⌋ r * \lfloor \frac{k}{i} \rfloor r ∗ ⌊ i k ⌋ , 公差为 ⌊ k i ⌋ \lfloor \frac{k}{i} \rfloor ⌊ i k ⌋ ) , 对于每一段区间计算和即可。
注意,A n s Ans A n s 计算的是 ∑ i = 1 n ⌊ k i ⌋ ∗ i \sum_{i=1}^n \lfloor \frac{k}{i} \rfloor * i ∑ i = 1 n ⌊ i k ⌋ ∗ i 。
#include <cstdio>
#include <iostream>
using namespace std;
int n , k;
long long Ans;
int main( ) {
scanf("%d %d",&n,&k);
for( int l = 1 , r ; l <= n ; l = r + 1 ) {
r = k / l == 0 ? n : min( n , k / ( k / l ) );
Ans += 1ll * ( k / l ) * ( l + r ) * ( r - l + 1 ) / 2;
}
printf("%lld", 1ll * n * k - Ans );
return 0;
}
四.莫比乌斯函数与莫比乌斯反演
1.莫比乌斯函数
由唯一分解定理得:
n = p 1 w 1 p 2 w 2 . . . p q w q n=p_1^{w_1}p_2^{w_2}...p_q^{w_q}
n = p 1 w 1 p 2 w 2 . . . p q w q
μ ( n ) = { 1 ( n = 1 ) ( − 1 ) q ( ∀ w i = 1 ) 0 ( ∃ w i ≥ 2 ) \mu(n)=\begin{cases}1 & (n=1)\\
(-1)^q & (\forall w_i=1) \\
0 & (\exists w_i \ge 2)
\end{cases}
μ ( n ) = ⎩ ⎪ ⎨ ⎪ ⎧ 1 ( − 1 ) q 0 ( n = 1 ) ( ∀ w i = 1 ) ( ∃ w i ≥ 2 )
通俗来讲,μ ( 1 ) = 1 \mu(1)=1 μ ( 1 ) = 1 ,当 n n n 存在平方因子时 μ ( n ) = 0 \mu(n)=0 μ ( n ) = 0
否则 μ ( n ) = ( − 1 ) k \mu(n)=(-1)^k μ ( n ) = ( − 1 ) k , k k k 为质因子数。
附一份线性筛的代码:
void sieve( int x ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= x ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
mu[ i ] = -1;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= x ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
}
2.莫比乌斯反演
1.形式1
如果
F ( n ) = ∑ d ∣ n f ( d ) F(n)=∑_{d|n}f(d)
F ( n ) = d ∣ n ∑ f ( d )
则有
f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=∑_{d|n}μ(d)F(\frac{n}{d})
f ( n ) = d ∣ n ∑ μ ( d ) F ( d n )
证法1.狄利克雷卷积
F = f ∗ I F=f*I
F = f ∗ I
F ∗ μ = f ∗ I ∗ μ F*\mu=f*I*\mu
F ∗ μ = f ∗ I ∗ μ
F ∗ μ = f ∗ ϵ F*\mu=f*\epsilon
F ∗ μ = f ∗ ϵ
f = F ∗ μ f=F*\mu
f = F ∗ μ
证法2.和式变化
∑ d ∣ n μ ( d ) F ( n d ) ~~~~~~~~~~~~~~~~~~~~∑_{d|n}μ(d)F(\frac{n}{d})
d ∣ n ∑ μ ( d ) F ( d n )
= ∑ d ∣ n μ ( d ) ∑ s ∣ n d f ( s ) ~~~~~~~~~~~~~~~~~~~~~=∑_{d|n}μ(d)\sum_{s|\frac{n}{d}}f(s)
= d ∣ n ∑ μ ( d ) s ∣ d n ∑ f ( s )
= ∑ d ∣ n f ( d ) ∑ s ∣ n d μ ( s ) ~~~~~~~~~~~~~~~~~~~~~=∑_{d|n}f(d)\sum_{s|\frac{n}{d}}\mu(s)
= d ∣ n ∑ f ( d ) s ∣ d n ∑ μ ( s )
= ∑ d ∣ n f ( d ) [ n d = 1 ] ~~~~~~~~~~~~~~~~~~~=∑_{d|n}f(d)[\frac{n}{d}=1]
= d ∣ n ∑ f ( d ) [ d n = 1 ]
= f ( n ) =f(n)
= f ( n )
2.形式2
如果
F ( n ) = ∑ n ∣ d f ( d ) F(n)=∑_{n|d}f(d)
F ( n ) = n ∣ d ∑ f ( d )
则有
f ( n ) = ∑ n ∣ d μ ( d ) F ( d n ) f(n)=∑_{n|d}μ(d)F(\frac{d}{n})
f ( n ) = n ∣ d ∑ μ ( d ) F ( n d )
1.证法1.和式变化
∑ n ∣ d μ ( d ) F ( d n ) ~~~~~~~~~~~~~~~~~~~~∑_{n|d}μ(d)F(\frac{d}{n})
n ∣ d ∑ μ ( d ) F ( n d )
= ∑ n ∣ d μ ( d ) ∑ d n ∣ s f ( s ) ~~~~~~~~~~~~~~~~~~~~~=∑_{n|d}μ(d)\sum_{\frac{d}{n}|s}f(s)
= n ∣ d ∑ μ ( d ) n d ∣ s ∑ f ( s )
= ∑ n ∣ d f ( d ) ∑ d n ∣ s μ ( s ) ~~~~~~~~~~~~~~~~~~~~~=∑_{n|d}f(d)\sum_{\frac{d}{n}|s}\mu(s)
= n ∣ d ∑ f ( d ) n d ∣ s ∑ μ ( s )
= ∑ n ∣ d f ( d ) [ d n = 1 ] ~~~~~~~~~~~~~~~~~~~=∑_{n|d}f(d)[\frac{d}{n}=1]
= n ∣ d ∑ f ( d ) [ n d = 1 ]
= f ( n ) =f(n)
= f ( n )
2.证法2.莫比乌斯函数
∑ n ∣ d μ ( d ) F ( d n ) ~~~~~~~~~~~~~~~~~~~~∑_{n|d}μ(d)F(\frac{d}{n})
n ∣ d ∑ μ ( d ) F ( n d )
= ∑ n ∣ d μ ( d n ) F ( d ) ~~~~~~~~~~~~~~~~~~~~=∑_{n|d}\mu(\frac{d}{n})F(d)
= n ∣ d ∑ μ ( n d ) F ( d )
= ∑ n ∣ d μ ( d n ) ∑ d ∣ s f ( s ) ~~~~~~~~~~~~~~~~~~~~~=∑_{n|d}\mu(\frac{d}{n})\sum_{d|s}f(s)
= n ∣ d ∑ μ ( n d ) d ∣ s ∑ f ( s )
因为 d d d , s s s 分别为 n n n , d d d 倍数, 所以设 d = n × k , s = d × t d=n \times k , s=d \times t d = n × k , s = d × t
= ∑ k = 1 μ ( k ) ∑ t = 1 f ( ( k × t ) × n ) ~~~~~~~~~~~~~~~~~~~~~=∑_{k=1}μ(k)\sum_{t=1}f( (k \times t) \times n)
= k = 1 ∑ μ ( k ) t = 1 ∑ f ( ( k × t ) × n )
观察发现,对于每一个 k k k ,它会将所有的倍数贡献 μ ( k ) \mu(k) μ ( k ) 个。
反过来将,对于一个f ( a n ) f(an) f ( a n ) ,它出现的次数为∑ d ∣ a μ ( d ) = [ a = 1 ] \sum_{d|a}\mu(d)=[a=1] ∑ d ∣ a μ ( d ) = [ a = 1 ] 。
所以只有当 a = 1 a=1 a = 1 时,f ( 1 ∗ n ) = f ( n ) f(1*n)=f(n) f ( 1 ∗ n ) = f ( n ) 会刚好出现一次。
所以上式等于 f ( n ) f(n) f ( n ) 。
3.例题
1.Luogu P3455 求 ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ] \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d] ∑ i = 1 n ∑ j = 1 m [ g c d ( i , j ) = d ] ( d d d 已知 )
题解
2.Luogu P1829 求 ∑ i = 1 n ∑ j = 1 m l c m ( i , j ) \sum_{i=1}^n\sum_{j=1}^mlcm(i,j) ∑ i = 1 n ∑ j = 1 m l c m ( i , j )
题解
3.cqbzoj P6388 求 ∑ i = 1 n ∑ j = 1 m g c d ( i , j ) \sum_{i=1}^n\sum_{j=1}^mgcd(i,j) ∑ i = 1 n ∑ j = 1 m g c d ( i , j )
题解
4.Luogu P3704 求 ∑ i = 1 n ∑ j = 1 m f g c d ( i , j ) \sum_{i=1}^n\sum_{j=1}^mf_{gcd(i,j)} ∑ i = 1 n ∑ j = 1 m f g c d ( i , j ) , f f f 为斐波拉契数列。
题解
五.杜教筛
一.前言
一般来说,反演的题目都需要积性函数的前缀和,一般都能用线性筛解决。
但是,如果良心出题人将 n n n 出到 1 0 9 10^9 1 0 9 , 我们就需要使用一种非线性时间筛法。
二.推导
首先设要计算的函数为 f f f , S S S 为其前缀和。
构造出两个函数 g g g , h h h , 使得 h = f ∗ g h=f * g h = f ∗ g , 即 h ( n ) = ∑ d ∣ n f ( d ) ∗ g ( n d ) h(n)=\sum_{d|n}f(d)*g(\frac{n}{d}) h ( n ) = ∑ d ∣ n f ( d ) ∗ g ( d n )
显然有:
∑ i = 1 n h ( i ) = ∑ i = 1 n ∑ d ∣ i g ( i d ) ∗ f ( d ) \sum_{i=1}^{n}h(i)=\sum_{i=1}^n\sum_{d|i}g(\frac{i}{d})* f(d)
i = 1 ∑ n h ( i ) = i = 1 ∑ n d ∣ i ∑ g ( d i ) ∗ f ( d )
∑ i = 1 n h ( i ) = ∑ i = 1 n ∑ d b = i g ( d ) ∗ f ( b ) \sum_{i=1}^{n}h(i)=\sum_{i=1}^n\sum_{db=i}g(d) * f(b)
i = 1 ∑ n h ( i ) = i = 1 ∑ n d b = i ∑ g ( d ) ∗ f ( b )
∑ i = 1 n h ( i ) = ∑ d = 1 n g ( d ) ∑ b = 1 ⌊ n d ⌋ f ( b ) \sum_{i=1}^{n}h(i)=\sum_{d=1}^ng(d)\sum_{b=1}^{\lfloor \frac{n}{d} \rfloor}f(b)
i = 1 ∑ n h ( i ) = d = 1 ∑ n g ( d ) b = 1 ∑ ⌊ d n ⌋ f ( b )
∑ i = 1 n h ( i ) = ∑ d = 1 n g ( d ) S ( ⌊ n d ⌋ ) \sum_{i=1}^{n}h(i)=\sum_{d=1}^ng(d)S(\lfloor \frac{n}{d} \rfloor)
i = 1 ∑ n h ( i ) = d = 1 ∑ n g ( d ) S ( ⌊ d n ⌋ )
∑ i = 1 n h ( i ) = g ( 1 ) S ( n ) + ∑ d = 2 n g ( d ) S ( ⌊ n d ⌋ ) \sum_{i=1}^{n}h(i)=g(1)S(n)+\sum_{d=2}^ng(d)S(\lfloor \frac{n}{d} \rfloor)
i = 1 ∑ n h ( i ) = g ( 1 ) S ( n ) + d = 2 ∑ n g ( d ) S ( ⌊ d n ⌋ )
g ( 1 ) S ( n ) = ∑ i = 1 n h ( i ) − ∑ d = 2 n g ( d ) S ( ⌊ n d ⌋ ) g(1)S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^ng(d)S(\lfloor \frac{n}{d} \rfloor)
g ( 1 ) S ( n ) = i = 1 ∑ n h ( i ) − d = 2 ∑ n g ( d ) S ( ⌊ d n ⌋ )
这就是杜教筛的一般形式了。
3.应用
一般来讲,在杜教筛时,h h h 的前缀和可以快速求得 , g g g 的前缀和也尽量简单。
大部分是狄利克雷卷积的形式。
1.求 S ( n ) = ∑ i = 1 n μ ( i ) S(n)=\sum_{i=1}^n\mu(i) S ( n ) = ∑ i = 1 n μ ( i )
容易想到 , μ ∗ I = ϵ \mu*I=\epsilon μ ∗ I = ϵ , 即 g g g 为 I I I , h h h 为 ϵ \epsilon ϵ 。
代入上式得:
S ( n ) = 1 − ∑ d = 2 n S ( ⌊ n d ⌋ ) S(n)=1-\sum_{d=2}^nS(\lfloor \frac{n}{d} \rfloor)
S ( n ) = 1 − d = 2 ∑ n S ( ⌊ d n ⌋ )
附一份代码:
int Summu( int n ) {
if( n <= MAXN ) return summ[ n ]; //预处理
if( Mapm[ n ] ) return Mapm[ n ]; //记忆化
int Ans = 1;
for( int l = 2 , r ; l <= n ; l = r + 1 ) {
r = n / ( n / l );
Ans -= ( r - l + 1 ) * Summu( n / l );
}
return Mapm[ n ] = Ans;
}
2.求 S ( n ) = ∑ i = 1 n φ ( i ) S(n)=\sum_{i=1}^n\varphi(i) S ( n ) = ∑ i = 1 n φ ( i )
容易想到 , φ ∗ I = i d \varphi*I=id φ ∗ I = i d , 即 g g g 为 I I I , h h h 为 i d id i d 。
代入上式得:
S ( n ) = n ∗ ( n + 1 ) 2 − ∑ d = 2 n S ( ⌊ n d ⌋ ) S(n)=\frac{n*(n+1)}{2}-\sum_{d=2}^nS(\lfloor \frac{n}{d} \rfloor)
S ( n ) = 2 n ∗ ( n + 1 ) − d = 2 ∑ n S ( ⌊ d n ⌋ )
附一份代码:
int Sumphi( int n ) {
if( n <= MAXN ) return sump[ n ]; //预处理
if( Mapp[ n ] ) return Mapp[ n ]; //记忆化
int Ans = n * ( n + 1 ) / 2;
for( int l = 2 , r ; l <= n ; l = r + 1 ) {
r = n / ( n / l );
Ans -= ( r - l + 1 ) * Sumphi( n / l );
}
return Mapp[ n ] = Ans;
}
结合 1 , 2 1,2 1 , 2 就是 P4213 【模板】杜教筛(Sum) 。
3.求 S ( n ) = ∑ i = 1 n φ ( i ) × i 2 S(n)=\sum_{i=1}^n\varphi(i) \times i^2 S ( n ) = ∑ i = 1 n φ ( i ) × i 2
在迪利克雷卷积中,$ id * id $ 会是一个非常好的式子,因为这样可以约分。
我们不妨构造函数 g ( n ) = n 2 g(n)=n^2 g ( n ) = n 2 , 来约掉f ( n ) f(n) f ( n ) 所含的n 2 n^2 n 2 。
h ( n ) = ∑ d ∣ n f ( d ) × g ( n d ) h(n)=\sum_{d|n}f(d) \times g(\frac{n}{d})
h ( n ) = d ∣ n ∑ f ( d ) × g ( d n )
= ∑ d ∣ n φ ( d ) × d 2 × ( n d ) 2 ~~ ~~~~~~~~~~~~~~~~ =\sum_{d|n}\varphi(d) \times d^2 \times (\frac{n}{d})^2
= d ∣ n ∑ φ ( d ) × d 2 × ( d n ) 2
= n 2 ∑ d ∣ n φ ( d ) = n 3 ~~ ~~~~~~~~~ =n^2\sum_{d|n}\varphi(d)=n^3
= n 2 d ∣ n ∑ φ ( d ) = n 3
h , g h,g h , g 前缀和非常容易得到
∑ i = 1 n h ( i ) = n 2 ( n + 1 ) 2 4 \sum_{i=1}^nh(i)=\frac{n^2(n+1)^2}{4} ∑ i = 1 n h ( i ) = 4 n 2 ( n + 1 ) 2
∑ i = 1 n g ( i ) = n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{i=1}^ng(i)=\frac{n(n+1)(2n+1)}{6} ∑ i = 1 n g ( i ) = 6 n ( n + 1 ) ( 2 n + 1 )
带入杜教筛的式子:
g ( 1 ) S ( n ) = ∑ i = 1 n h ( i ) − ∑ d = 2 n g ( d ) S ( ⌊ n d ⌋ ) g(1)S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^ng(d)S(\lfloor \frac{n}{d} \rfloor)
g ( 1 ) S ( n ) = i = 1 ∑ n h ( i ) − d = 2 ∑ n g ( d ) S ( ⌊ d n ⌋ )
S ( n ) = n 2 ( n + 1 ) 2 4 − ∑ d = 2 n g ( d ) S ( ⌊ n d ⌋ ) S(n)=\frac{n^2(n+1)^2}{4}-\sum_{d=2}^ng(d)S(\lfloor \frac{n}{d} \rfloor)
S ( n ) = 4 n 2 ( n + 1 ) 2 − d = 2 ∑ n g ( d ) S ( ⌊ d n ⌋ )
然后就可以做 P3768 简单的数学题
参考题解
4.求 S ( n ) = ∑ i = 1 n d ( i ) S(n)=\sum_{i=1}^n d(i) S ( n ) = ∑ i = 1 n d ( i )
首先有 d = I ∗ I d=I*I d = I ∗ I
容易想到 , μ ∗ d = I \mu*d=I μ ∗ d = I , 即 g g g 为 μ \mu μ , h h h 为 I I I 。
代入上式得:
S ( n ) = n − ∑ d = 2 n μ ( d ) S ( ⌊ n d ⌋ ) S(n)=n-\sum_{d=2}^n \mu(d)S(\lfloor \frac{n}{d} \rfloor)
S ( n ) = n − d = 2 ∑ n μ ( d ) S ( ⌊ d n ⌋ )
然后可以用杜教筛同步筛 出 μ \mu μ 和 d d d 的前缀和。
原题 P6788 「EZEC-3」四月樱花
参考资料
数论函数
莫比乌斯反演
杜教筛